package com.eloancn.leecode.linkedList;


/**
 * leecode 21 合并两个有序的链表
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
 * @author lihepeng
 * 
 *
 */
public class Meger2LinkList {
	/**
	 * 使用递归操作完成两个有序链表合并
	 * @param l1
	 * @param l2
	 */
	public ListNode mergefunc1(ListNode l1, ListNode l2) {
		if(l1 == null) {
			return l2;
		}else if(l2 ==null) {
			return l1;
		}else if(l1.value<l2.value) {
			l1.next = mergefunc1(l1.next, l2);
			return l1;
		}else {
			l2.next = mergefunc1(l1, l2.next);
			return l2;
		}
		
	}
	/**
	 * 使用遍历的方式完成合并
	 * @param l1
	 * @param l2
	 * @return
	 */
	public ListNode mergefunc2(ListNode l1, ListNode l2) {
		ListNode preNode  =  new ListNode(-1);
		ListNode prev = preNode;
		while(l1!=null && l2!=null) {
			if (l1.value<l2.value) {
				prev.next = l1;
				l1 = l2.next;
			}else {
				prev.next = l2;
				l2 = l2.next;
			}
			prev = prev.next;
		}
		prev.next = l1==null?l2:l1;
		
		return preNode;
	}
	
}
